A circuit design layout, such as an integrated circuit (“IC”), a printed circuit board (PCB), an IC package, etc. is a device (e.g., a semiconductor device) that includes many electronic components, such as transistors, resistors, diodes, and so on. These components are often interconnected to form multiple circuit components, such as gates, cells, memory units, arithmetic units, controllers, decoders, etc. A circuit design layout includes multiple layers of wiring that interconnect its electronic and circuit components. Traditionally, circuit design layouts use preferred direction (“PD”) wiring models, which specify a preferred wiring direction for each of their wiring layers. In preferred direction wiring models, the preferred direction typically alternates between successive wiring layers. One example of a PD wiring model is the PD Manhattan wiring model, which specifies alternating layers of preferred-direction horizontal and vertical wiring.
Design engineers design the IC's and PCB's by transforming logical or circuit descriptions of the IC's or PCB's into geometric descriptions, called layouts. These layouts typically include (1) circuit modules (i.e., geometric representations of electronic or circuit IC components) with pins, and (2) interconnect lines (i.e., geometric representations of wiring) that connect the pins of the circuit modules. A net is typically defined as a collection of pins that need to be connected. A list of all or some of the nets in a layout is referred to as a net list.
To create layouts, design engineers typically use electronic design automation (“EDA”) applications. These applications provide sets of computer-based tools for creating, editing, and analyzing layouts for IC design, Printed Circuit Board (PCB) designs, or Packages. One EDA tool is a router that defines routes for interconnect lines that typically connect the pins of the nets.
The underlying engine for essentially all modern routers is a path finding algorithm, herein called the Single Connection Router (SCR). The SCR selects a particular path (or route) from one or more source locations (called pads) on one or more layers to one or more target locations (also pads) on one or more layers.
Potential paths are considered by “expanding” from one location to the next, starting with the location of the source (or one of the potential source locations) and ending with the target location (or one of several potential target locations). In a gridded-router, the expansion proceeds from one cell to an adjacent cell on the same layer or to the corresponding cell on another layer.
In a topological router, the expansion proceeds along the topological map from one channel to the next or to another layer. A topological route is a route that is defined in terms of its relation to other layout items, such as pins, obstacles, boundaries, and/or other topological routes of other nets. As such, a topological route provides a general plan for how to route a net, without necessarily providing a specific geometric path to do so. One topological route represents a set of diffeomorphic geometric routes (i.e., a set of geometric routes that can be morphed into one another through a continuous sequence of perturbations without changing the route's path relative to any other pin, path, or obstacle).
The path selection process described above is controlled by means of cost functions. Costs are typically computed for each expansion and then added together to get a partial subtotal to reach from its source up to the current location. Costs have numeric value (for example, higher is worse). The SCR finds the path from a source location to a target location with the lowest total cost that satisfies all the predetermined rules. This cost is typically computed as the sum of several different individual costs, such as direction, length, accumulated crosstalk, etc. The direction cost is usually charged whenever the direction of the expansion differs from the “preferred direction” for that layer. For example, routing vertically on a horizontal layer is considered a “wrong-way” and incurs an extra “wrong-way cost”.
The overall quality of the routing is directly determined by the cost computation. Better algorithms for computing costs result in better routing, where better might mean faster (fewer potential paths considered) or higher quality (higher likelihood of 100% completion) or some combination. Improvements to the underlying cost computation directly account for significant differences between competing routing products. Therefore, it is critical to the success of any router to use the best possible cost algorithms.
Historically, almost all routers (for IC, PCB and Packages) have been Manhattan routers. In a Manhattan (or horizontal/vertical) router, most routing etch on some layers is horizontal and most routing etch on the other layers is vertical. When selecting paths, the SCR would insert a via (a connection between layers) to connect the horizontal etch segments on one layer with the vertical segments on the other layer. This technique is still used in some IC routers where the size of a via is relatively small compared to the size of etch segments.
Some fabrication technologies used in manufacturing IC's do not allow any vertical routing on a horizontal layer or any horizontal routing on a vertical layer due to lithography limitations. For instance, FIG. 1 illustrates an example of horizontal routing and FIG. 2 illustrates an example of vertical routing. In these figures, etch segments are shown in black and vias are shown in grey. As shown, in this example, via locations are the same on both layers.
Some IC routers and PCB routers have implemented a wrong-way cost. This allows some horizontal routing on vertical layers and some vertical routing on horizontal layers but makes the cost higher than staying with the layer's preferred routing direction. FIG. 3 illustrates an example of wrong-way on routing on a vertical layer. During initial routing passes, this cost is typically very high which causes a strong bias against wrong-way routing. In later passes, this cost is typically reduced to allow the router to use wrong-way routing when needed to resolve difficult routing situations.
A few routers have allowed more than just vertical and horizontal routing directions. They might, for example, support layers with a +45° or −45° bias or other angles. Some gridded routers have automatically flipped the preferred routing direction along the edge of the design. For example, on a gridded-design, there is no point in preferring horizontal routing in cells along the east or west edge of the design, since there is no adjacent cell in that direction.
Some routers allow users to manually override the preferred routing direction for a particular region of the design. For example, this would allow the user to change the preferred routing direction on the north side of a ball grid array (BGA) to be vertical on all layers, even on layers with horizontal preferred directions. However, forcing the user to manually override the preferred routing direction for each section of the design is slow, tedious and error prone. It limits the “what if” planning that the user can explore.
Adjusting routing directions only around the outer perimeter of the design had some advantage many years ago because it allowed some routing to go all the way around the outside, thus completing the last few connections. However, most of the congestion is near high-pin count devices. Also, most nets have length limitations which disallow very long connections. Thus, flipping the preferred routing direction only around the outside edge of the design has limited value in modern routers. Therefore, there is a need in the art for a general mechanism to allow the router to automatically adjust the preferred routing direction for a region of the design.